package q340_lengthOfLongestSubstringKDistinct;

import java.util.LinkedHashMap;
import java.util.Map;

public class Solution_2 {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        if (n * k == 0) return 0;

        int left = 0;
        int right = 0;
        LinkedHashMap<Character, Integer> hashmap = new LinkedHashMap<>(k + 1);

        int max_len = 1;

        while (right < n) {
            Character character = s.charAt(right);
            if (hashmap.containsKey(character)) hashmap.remove(character);

            hashmap.put(character, right++);

            if (hashmap.size() == k + 1) {
                Map.Entry<Character, Integer> leftmost = hashmap.entrySet().iterator().next();// 该方法能够拿到最左字符位置
                hashmap.remove(leftmost.getKey());
                left = leftmost.getValue() + 1;
            }

            max_len = Math.max(max_len, right - left);
        }
        return max_len;
    }

}
